package 第一讲基础算法;

import java.util.Scanner;

public class AcWing787 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] arr=new int[n];
		for(int i=0;i<arr.length;i++) {
			arr[i]=sc.nextInt();
		}
		sc.close();
		mergesort(arr,0,n-1);
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		
	}
	
	public static void mergesort(int[] arr,int l,int r) {
		if(l>=r) {
			return;
		}
		//分界点
		int mid=l+r>>1;
		//递归解决子问题
		mergesort(arr,l,mid);
		mergesort(arr,mid+1,r);
		//合二为一
		int[] tmp=new int[r-l+1];
		int k=0,i=l,j=mid+1;
		while(i<=mid&&j<=r) {
			if(arr[i]<=arr[j]) {//一定要是小于等于，保证稳定性。因为mid前面和后面出现相等的数，为了稳定性，肯定得先取前面得数据才能保证相对位置
				tmp[k++]=arr[i++];
			}else {
				tmp[k++]=arr[j++];
			}
		}
		while(i<=mid)tmp[k++]=arr[i++];
		while(j<=r)tmp[k++]=arr[j++];
		for(i=l,j=0;i<=r&&j<=r-l;i++,j++) {
			arr[i]=tmp[j];
		}
	}

}
